package com.example.demo.leetcode.classics150;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _63删除链表的倒数第N个结点
 * @description
 * @date 2023/07/28 17:07
 * <p>
 * ******************************************************
 */
public class _63删除链表的倒数第N个结点 {

    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 虚拟节点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode p, q;
        p = q = dummy;
        int i = 0;
        /**
         * 第一步 假设设链表为1，2，3，4，5  n为2
         * p 链表 -1， 1，2，3，4，5
         * q 链表 -1， 1，2，3，4，5
         *
         * 第二步 p移动到n节点
         * p 链表 2，3，4，5
         * q 链表 -1， 1，2，3，4，5
         *
         * 第三步 pq同时往后移，直至p.next为空
         * p 链表 null
         * q 链表 3，4，5
         *
         * 第四步q.next = q.next.next;
         * q 链表 3，5
         *
         * 返回dummy.next
         */
        // p节点移到n指标
        while (p != null && i < n) {
            p = p.next;
            i++;
        }
        while (p.next != null) {
            p = p.next;
            q = q.next;
        }
        q.next = q.next.next;
        return dummy.next;
    }


    public ListNode removeNthFromEnd1(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode p, q;
        p = q = dummy;
        int i = 0;
        while (p != null && i < n) {
            p = p.next;
            i++;
        }

        while (p.next != null) {
            p = p.next;
            q = q.next;
        }

        q.next = q.next.next;

        return dummy.next;

    }


    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
